Subdivision schemes for the fair discretization of the spherical motion group

We present two subdivision schemes for the fair discretization of the spherical motion group. The first one is based on the subdivision of the 600-cell according to the tetrahedral/octahedral subdivision scheme in [S. Schaefer, J. Hakenberg, J. Warren, Smooth subdivision of tetrahedral meshes, in: R. Scopigno, D. Zorin (Eds.), Eurographics Symposium on Geometry Processing, 2004, pp. 151–158]. The second presented subdivision scheme is based on the spherical kinematic mapping. In the first step we discretize an elliptic linear congruence by the icosahedral discretization of the unit sphere. Then the resulting lines of the elliptic three-space are discretized such that the difference in the maximal and minimal elliptic distance between neighboring grid points becomes minimal.     

The Ramsey number for hypergraph cycles I

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁,…,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,…,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C_n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.     

A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A Genetic Algorithm for the Allocation of Buffer Storage Capacities in a Production Line with Unreliable Machines

In this paper, we consider a flow-line manufacturing system organized as a series of workstations separated by finite buffers. The failure and repair times of machines are supposed to be exponentially distributed. The production rate of each machine is deterministic, and different machines may have different production rates. The buffer allocation problem consists in determining the buffer capacities with respect to a given optimality criterion, which depends on the average production rate of the line, the buffer acquisition and installation cost, and the inventory cost. For this problem we propose a genetic algorithm where the tentative solutions are evaluated with an approximate method based on the Markov-model aggregation approach.     

A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Let X_n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X_n. The basic observation for its proof is that the probability distributions of are recursively defined by , where D_n is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the complexity of the independent set problem in triangle graphs

We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G−I, there is a vertex w∈I such that {u,v,w} is a triangle in G. We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are NP-complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P=NP.     

clever or smart: Strategies for the online target date assignment problem

In this paper, we consider the Online Target Date Assignment Problem (OnlineTDAP) for general downstream problems, where the downstream cost are nonnegative, additive and satisfy the triangle inequality.We analyze algorithm smart, which was introduced by Angelelli et al. [3] and give its exact competitive ratio depending on the number of requests. Since the obtained competitive ratio is at most we answer the question posed in Angelelli et al. [4] if smart has a competitive ratio strictly less than 2.Moreover, we introduce a new algorithm called clever and show that this strategy has a competitive ratio of 3/2. We show that this is asymptotically optimal by proving that no online algorithm can perform better than 3/2−ε.     

The complexity of dissociation set problems in graphs

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.